package com.adaydayup.week_0919;

import java.util.LinkedList;
import java.util.List;

public class AwareOfSecret {

    public static void main(String[] args) {
        int a = secret(6, 2, 4);
        int b = secret(6, 2, 4);

        AwareOfSecret as = new AwareOfSecret();

        int c = as.secretQuere(6, 2, 4);
//        int d = as.secretIndex(6, 2, 4);
        System.out.println(c);
//        System.out.println(d);

    }


    //递推 (i - forget, i - delay]
    private static int secret(int n, int delay, int forget) {
        int mod = 1000000007;
        int[][] f = new int[n + 1][n + 1];
        f[1][0] = f[0][1] = 1;
        for (int i = 2; i <= n; i++) {
            int l = Math.max(0, i - forget);
            int r = Math.max(0, i - delay);
            f[i][0] = (f[0][r] - f[0][l] + mod) % mod;
            f[0][i] = (f[0][i - 1] + f[i][0]) % mod;
        }
        return (f[0][n] - f[0][Math.max(0, n - forget)] + mod) % mod;
    }

    //dfs
    int n, delay, forget;
    int mod = 1000000007;
    int[] memo;

    private int secretDFS(int _n, int _delay, int _forget) {
        n = _n;
        delay = _delay;
        forget = _forget;
        memo = new int[n + 1];
        return dfs(1);
    }

    private int dfs(int i) {
        if (i + delay > n) return 1;
        if (memo[i] != 0) return memo[i];

        int a = i + delay, b = Math.min(i + forget - 1, n);
        long res = i + forget <= n ? 0 : 1;
        for (int j = a; j <= b; j++) {
            int t = dfs(j);
            memo[j] = t;
            res = (res + t) % mod;
        }
        return (int) res;
    }

    //队列
    private int secretQuere(int n, int delay, int forget) {
        int[] arr = new int[n + 1];
        arr[1] = 1;
        int i, j;
        for (i = 1; i <= n; ++i) {
            for (j = i + delay; j < i + forget && j <= n; ++j) {
                arr[j] += arr[i];
                if (arr[j] >= mod) arr[j] -= mod;
            }
        }
        int sum = 0;
        for (i = n - forget + 1; i <= n; ++i) {
            sum += arr[i];
            if (sum >= mod) sum -= mod;
        }
        return sum;
    }
    //索引
    private int secretIndex(int n, int delay, int forget) {
        List<int[]> que = new LinkedList<>();
        // 第1天，该组只有一个人知到秘密，且它将来可以传播秘密。
        // que的size维持在forget大小，毕竟过了就忘了，在这期间，大于等于delay后的才能传播秘密。
        que.add(new int[]{1, 1 + delay, 1 + forget});// 第1天为第1天时知道秘密。
        int ans = 1;
        for (int i = 2; i <= n; i++) {
            // 将忘记秘密的一组人移除队列。
            while (!que.isEmpty() && que.get(0)[2] <= i) {
                // 知道秘密的人流失。
                ans -= que.get(0)[0];
                ans = (ans + mod) % mod;
                // 他已经不能传播秘密了。
                que.remove(0);
            }
            // 取今天能传播多少人，并将其加到ans中。
            int spreed = 0;
            for (int j = 0; j < que.size(); j++) {
                if (i >= que.get(j)[1]) {
                    spreed += que.get(j)[0];
                    spreed %= mod;
                }
            }
            // 得到传播总人数，不断累计。
            ans = (ans + spreed) % mod;
            // 并将其加入队列。
            que.add(new int[]{spreed, i + delay, i + forget});
        }
        return ans;//5 2 3
    }



}
